|
A solved game is a game whose outcome (win, lose, or draw) can be correctly predicted from any position, given that both players play perfectly. Games which have not been solved are said to be "unsolved". Games for which only some positions have been solved are said to be "partially solved". This article focuses on two-player games that have been solved. ==Overview== A two-player game can be "solved" on several levels:〔V. Allis, ''Searching for Solutions in Games and Artificial Intelligence.'' PhD thesis, Department of Computer Science, University of Limburg, 1994. Online: (pdf )〕〔H. Jaap van den Herik, Jos W.H.M. Uiterwijk, Jack van Rijswijck, ''Games solved: Now and in the future'', Artificial Intelligence 134 (2002) 277–311.〕 ;Ultra-weak : Prove whether the first player will win, lose, or draw from the initial position, given perfect play on both sides. This can be a non-constructive proof (possibly involving a strategy-stealing argument) that need not actually determine any moves of the perfect play. ;Weak : Provide an algorithm that secures a win for one player, or a draw for either, against any possible moves by the opponent, from the beginning of the game. That is, produce at least one complete ideal game (all moves start to end) with proof that each move is optimal for the player making it. It does not necessarily mean a computer program using the solution will play optimally against an imperfect opponent. For example, the checkers program Chinook will never turn a drawn position into a losing position (since the weak solution of checkers proves that it is a draw), but it might possibly turn a winning position into a drawn position because Chinook does not expect the opponent to play a move that will not win but could possibly lose, and so it does not analyze such moves completely. ;Strong : Provide an algorithm that can produce perfect play (moves) from any position, even if mistakes have already been made on one or both sides. Despite the name, many game theorists believe that "ultra-weak" are the deepest, most interesting and valuable proofs. "Ultra-weak" proofs require a scholar to reason about the abstract properties of the game, and show how these properties lead to certain outcomes if perfect play is realized. By contrast, "strong" proofs often proceed by brute force—using a computer to exhaustively search a game tree to figure out what would happen if perfect play were realized. The resulting proof gives an optimal strategy for every possible position on the board. However, these proofs aren't as helpful in understanding deeper reasons why some games are solvable as a draw, and other, seemingly very similar games are solvable as a win. Given the rules of any two-person game with a finite number of positions, one can always trivially construct a minimax algorithm that would exhaustively traverse the game tree. However, since for many non-trivial games such an algorithm would require an infeasible amount of time to generate a move in a given position, a game is not considered to be solved weakly or strongly unless the algorithm can be run by existing hardware in a reasonable time. Many algorithms rely on a huge pre-generated database, and are effectively nothing more. As an example of a strong solution, the game of tic-tac-toe is solvable as a draw for both players with perfect play (a result even manually determinable by schoolchildren). Games like nim also admit a rigorous analysis using combinatorial game theory. Whether a game is solved is not necessarily the same as whether it remains interesting for humans to play. Even a strongly solved game can still be interesting if its solution is too complex to be memorized; conversely, a weakly solved game may lose its attraction if the winning strategy is simple enough to remember (e.g. Maharajah and the Sepoys). An ultra-weak solution (e.g. Chomp or Hex on a sufficiently large board) generally does not affect playability. Moreover, even if the game is not solved, it is possible that an algorithm yields a good approximate solution: for instance, an article in ''Science'' from January 2015 claims that their heads up limit Texas hold 'em poker bot Cepheus guarantees that a human lifetime of play is not sufficient to establish with statistical significance that its strategy is not an exact solution. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Solved game」の詳細全文を読む スポンサード リンク
|